package leetcode;

public class Lc33 {

    public int search(int[] nums, int target) {

        if (nums.length == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int k = getK(nums,0, nums.length - 1);
        int idx = binarySearch(nums, target, 0, k);
        if (idx == -1) {
            return binarySearch(nums, target, k + 1, nums.length - 1);
        }
        return idx;
    }

    public int binarySearch(int[] nums, int target, int l, int r) {
        if (l > r)
            return -1;
        int mid = (l + r) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] > target) {
            return binarySearch(nums, target, l, mid - 1);
        }
        if (nums[mid] < target) {
            return binarySearch(nums, target, mid + 1, r);
        }
        return -1;
    }

    int getK(int[] nums, int l, int r) {

        if (l > r) {
            return -1;
        }

        int mid = (l + r) / 2;
        if (mid == 0) {
            if (nums[mid] > nums[mid + 1]) {
                return mid;
            }
            return getK(nums, mid + 1, r);
        } else if (mid == nums.length - 1) {
            if (nums[mid] < nums[mid - 1]) {
                return mid;
            }
            return getK(nums, l, mid - 1);
        } else {
            if (nums[mid] > nums[mid + 1] ) {
                return mid;
            } else if (nums[mid] < nums[mid - 1]) {
                return mid - 1;
            }else {
                int ind = getK(nums, l, mid - 1);
                if (ind != -1) {
                    return ind;
                }
                return getK(nums, mid + 1, r);
            }
        }
    }

//    public static void main(String[] args) {
//        Lc33 lc33 = new Lc33();
//        int[] nums = {4,5,6,7,0,1,2};
//        int target = 7;
//        System.out.println(lc33.search(nums, target));
//    }

}
